
#ifndef _RadixTree_h_
#define _RadixTree_h_

#include <string>
#include <vector>

typedef int WordId;
const WordId NotWord = -1;

class RadixTreeNode
{
public:
	enum MatchType { MatchStrictly, MatchPartial };

	RadixTreeNode( const ::std::string& word, WordId id, MatchType mt );
	~RadixTreeNode();

private:
	RadixTreeNode*	m_left;		// left node for children
	RadixTreeNode* 	m_right;	// right node for brothers
	::std::string	m_prefix;
	WordId			m_id;
	MatchType		m_matchtype;

	WordId insert( const ::std::string& word, WordId id, MatchType mt );
	/*
	 * if return NotWord(-1), unsuccess to find the word
	 */
	WordId search( const ::std::string& word );
	bool check( const ::std::string& word, size_t pos, ::std::string& checkword );
	size_t matchPrefix( const ::std::string& word );

friend class RadixTree;
};

class RadixTree
{
public:
	RadixTree();
	~RadixTree();

	WordId insert( const ::std::string& word, WordId id, RadixTreeNode::MatchType mt );
	WordId search( const ::std::string& word );
	bool check( const ::std::string& word, ::std::string& checkword );

private:
	::std::vector< RadixTreeNode* >  m_root_vector;
};

#endif

